{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Target Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTargetSumWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #目标和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数数组 <code>nums</code> 和一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>向数组中的每个整数前添加&nbsp;<code>'+'</code> 或 <code>'-'</code> ，然后串联起所有整数，可以构造一个 <strong>表达式</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>nums = [2, 1]</code> ，可以在 <code>2</code> 之前添加 <code>'+'</code> ，在 <code>1</code> 之前添加 <code>'-'</code> ，然后串联起来得到表达式 <code>\"+2-1\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回可以通过上述方法构造的、运算结果等于 <code>target</code> 的不同 <strong>表达式</strong> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,1,1], target = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一共有 5 种方法让最终目标和为 3 。\n",
    "-1 + 1 + 1 + 1 + 1 = 3\n",
    "+1 - 1 + 1 + 1 + 1 = 3\n",
    "+1 + 1 - 1 + 1 + 1 = 3\n",
    "+1 + 1 + 1 - 1 + 1 = 3\n",
    "+1 + 1 + 1 + 1 - 1 = 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1], target = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 20</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= sum(nums[i]) &lt;= 1000</code></li>\n",
    "\t<li><code>-1000 &lt;= target &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [target-sum](https://leetcode.cn/problems/target-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [target-sum](https://leetcode.cn/problems/target-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,1,1]\\n3', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        dp = {}\n",
    "        def helper(i, cur):\n",
    "            if i == len(nums):\n",
    "                return 1 if cur == target else 0\n",
    "            if (i, cur) in dp:\n",
    "                return dp[(i, cur)]\n",
    "            dp[(i, cur)] = helper(i+1, cur+nums[i])+helper(i+1, cur-nums[i])\n",
    "            return dp[(i, cur)]\n",
    "        return helper(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        Sum = sum(nums)\n",
    "        if Sum<S or (Sum+S)%2>0:\n",
    "            return 0\n",
    "        S = (Sum+S)>>1\n",
    "        DP = [0]*(S+1)\n",
    "        DP[0] = 1\n",
    "        for n in nums:\n",
    "            for i in range(S,n-1,-1):\n",
    "                DP[i] += DP[i-n]\n",
    "        return DP[S]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cnt = {0: 1}\n",
    "        for n in nums:\n",
    "            d = {}\n",
    "            for c in cnt:\n",
    "                d[c + n] = d.get(c + n, 0) + cnt[c]\n",
    "                d[c - n] = d.get(c - n, 0) + cnt[c]\n",
    "            cnt = d\n",
    "        return cnt.get(S, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        l = defaultdict(int)\n",
    "        l[-nums[0]] += 1\n",
    "        l[nums[0]] += 1\n",
    "        for num in nums[1:]:\n",
    "            cur = defaultdict(int)\n",
    "            for val in l:\n",
    "                cur[val+num] += l[val]\n",
    "                cur[val-num] += l[val]\n",
    "            l = cur\n",
    "        return l[S]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sum_nums = sum(nums)\n",
    "        if sum_nums < S or -sum_nums > S:\n",
    "            return 0\n",
    "        \n",
    "        len_nums = len(nums)\n",
    "        mem = [[0]*(2*sum_nums + 1) for _ in range(len_nums+1)]\n",
    "        mem[0][sum_nums] = 1\n",
    "        for i in range(1, len_nums + 1):\n",
    "            for j in range(2*sum_nums + 1):\n",
    "                if j + nums[i - 1] < 2*sum_nums + 1:\n",
    "                    mem[i][j] += mem[i - 1][j + nums[i - 1]]\n",
    "                if j - nums[i - 1] >= 0:\n",
    "                    mem[i][j] += mem[i - 1][j - nums[i - 1]]\n",
    "                    \n",
    "        return mem[len_nums][sum_nums + S]      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if len(nums) < 1 or (sum(nums) < S) or (-sum(nums) > S): return 0\n",
    "        numssum = sum(nums)\n",
    "        w = [[0 for i in range(2*numssum+1)] for j in range(len(nums))]  \n",
    "        for i, v in enumerate(nums):\n",
    "            if  i == 0:\n",
    "                w[i][numssum+v] += 1\n",
    "                w[i][numssum-v] += 1\n",
    "                continue\n",
    "            for j in range(0, 2*numssum+1):\n",
    "                if w[i-1][j] != 0:\n",
    "                     w[i][j+v] += w[i-1][j]\n",
    "                     w[i][j-v] += w[i-1][j]\n",
    "        return w[-1][numssum+S]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [dict() for i in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(n):\n",
    "            for k,v in dp[i].items():\n",
    "                dp[i+1][k+nums[i]] = dp[i+1].get(k+nums[i],0) + v\n",
    "                dp[i+1][k-nums[i]] = dp[i+1].get(k-nums[i],0) + v\n",
    "        return dp[n].get(S,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if not nums:\n",
    "        #     return 0\n",
    "        # def helper(index, target):\n",
    "        #     if index == len(nums):\n",
    "        #         if target == S:\n",
    "        #             return 1\n",
    "        #         else:\n",
    "        #             return 0\n",
    "        #     return helper(index+1, target+nums[index]) + helper(index+1, target-nums[index])\n",
    "        # return helper(0, 0)\n",
    "        \n",
    "        length = len(nums)\n",
    "        dp = [collections.defaultdict(int) for _ in range(length+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i, num in enumerate(nums):\n",
    "            for key,value in dp[i].items():\n",
    "                dp[i+1][key+num] += value\n",
    "                dp[i+1][key-num] += value\n",
    "        return dp[length][S]\n",
    "    \n",
    "        \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, S):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 暴力破解(dfs)的时间复杂度是O(2^n)\n",
    "        # 使用dp能稍微降低一下时间复杂度\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(len(nums))]\n",
    "        # edge case\n",
    "        dp[0][nums[0]] += 1\n",
    "        dp[0][-nums[0]] += 1\n",
    "        # dp\n",
    "        for i in range(1, len(nums)):\n",
    "            for total in dp[i-1]:\n",
    "                dp[i][total+nums[i]] += dp[i-1][total]\n",
    "                dp[i][total-nums[i]] += dp[i-1][total]\n",
    "        return dp[n-1][S]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:\n",
    "        #positive -neigative = S\n",
    "        #positive + neigative = sum(nums)\n",
    "        #2*positive = S+sum(nums)\n",
    "        #positive = (S+sum(nums))/2\n",
    "        n = sum(nums)\n",
    "        if n<S:\n",
    "            return 0\n",
    "        if (S+n) %2:\n",
    "            return 0\n",
    "        target = int((S+n)/2)\n",
    "        dp=[0 for _ in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in nums:\n",
    "            if i <=target:\n",
    "                j=target\n",
    "                while j>=i:\n",
    "                    dp[j] = dp[j]+dp[j-i]\n",
    "                    j-=1\n",
    "        return dp[-1]\n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:  \n",
    "        sums = sum(nums)      \n",
    "        target = S + sums\n",
    "        if target % 2 or S > sums: return 0\n",
    "        target = target // 2        \n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for num in nums:\n",
    "            for j in range(target, num - 1, -1):\n",
    "                dp[j] += dp[j - num]            \n",
    "        return dp[-1]    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(idx, cur):\n",
    "        #     if idx < self.n and (idx, cur) not in dic:\n",
    "        #         dic[(idx, cur)] = dfs(idx + 1, cur + nums[idx]) + dfs(idx + 1, cur - nums[idx])\n",
    "        #     return dic.get((idx, cur), int(cur == S))           \n",
    "       \n",
    "        # self.n, dic = len(nums), {}\n",
    "        # return dfs(0, 0)       \n",
    "        \n",
    "\n",
    "\n",
    "        # d = {}\n",
    "        # def dfs(cur, i, d):\n",
    "        #     if i < len(nums) and (cur, i) not in d: # 搜索周围节点\n",
    "        #         d[(cur, i)] = dfs(cur + nums[i], i + 1, d) + dfs(cur - nums[i],i + 1, d)\n",
    "        #     return d.get((cur, i), int(cur == S))   \n",
    "        # return dfs(0, 0, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findTargetSumWays(self, nums, S: int):\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += num\n",
    "        if sum < S or (sum + S) % 2 == 1:\n",
    "            return 0\n",
    "\n",
    "        return self.subsets(nums, int((sum + S) / 2))\n",
    "\n",
    "    def subsets(self, nums: list, sum: int):\n",
    "        n = len(nums)\n",
    "        dp = [0] * (sum+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(sum, -1, -1):\n",
    "                if j >= nums[i-1]:\n",
    "                    dp[j] = dp[j] + dp[j-nums[i-1]]\n",
    "                else:\n",
    "                    dp[j] = dp[j]\n",
    "        return dp[sum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:\n",
    "        total = sum(nums)\n",
    "        if total  < S or (S + total) % 2: return 0\n",
    "        target = (S + total) // 2\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for num in nums:\n",
    "            for i in range(target, num-1, -1):\n",
    "                dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += num\n",
    "        \n",
    "        if(S>sum or -S>sum): return 0\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [[0] * (sum*2+1) for _ in range(n)]\n",
    "        \n",
    "        dp[0][nums[0]+sum] += 1   # 使用 += 是因为有可能 nums[0] 为 0\n",
    "        dp[0][-nums[0]+sum] += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(-sum, sum+1):\n",
    "                pre = 0 if(j-nums[i] < -sum ) else dp[i-1][j-nums[i]+sum]\n",
    "                pos = 0 if(j+nums[i] > sum )  else dp[i-1][j+nums[i]+sum]\n",
    "                dp[i][j+sum] = pre + pos\n",
    "\n",
    "        return dp[-1][S+sum]\n",
    "\n",
    "\n",
    "            \n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        if (sum(nums) + target)%2 == 1:return 0\n",
    "        if abs(target) > sum(nums):return 0  #没有方案\n",
    "        bag_weight = (sum(nums) + target)//2\n",
    "        dp = [0] * (bag_weight + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(bag_weight, nums[i]-1, -1):\n",
    "                dp[j] += dp[j-nums[i]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # P + N = sum\n",
    "        # P - N = target\n",
    "        # P = (sum+taget)/2\n",
    "\n",
    "        postive_sum = (sum(nums)+target)//2\n",
    "        # print(postive_sum)\n",
    "        if (sum(nums)+target) % 2 == 1:\n",
    "            return 0\n",
    "        if postive_sum <0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0] * (postive_sum+1)\n",
    "        dp[0] = 1\n",
    "        for num in nums:\n",
    "            for j in range(postive_sum,-1,-1):\n",
    "                if num <= j:\n",
    "                    dp[j] = dp[j] + dp[j-num]\n",
    "        return dp[postive_sum]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        Sum = sum(nums)\n",
    "        if Sum < abs(target):\n",
    "            return 0\n",
    "        Sum += target\n",
    "        if Sum % 2 == 1:\n",
    "            return 0\n",
    "        Sum //= 2\n",
    "        dp = [0] * (Sum + 1)\n",
    "        dp[0] = 1\n",
    "        for num in nums:\n",
    "            for j in range(Sum, num - 1, - 1):\n",
    "                dp[j] += dp[j - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        total = sum(nums)\n",
    "        #pos+neg = total ,pos-neg = target\n",
    "        if (total+target)%2 == 1:\n",
    "            return 0\n",
    "        if abs(target)>total:\n",
    "            return 0\n",
    "        pos = (total+target)//2 \n",
    "        neg = (total-target)//2\n",
    "        amount = min(pos,neg)\n",
    "        n = len(nums)\n",
    "        dp = [[0]*(amount+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(amount+1):\n",
    "                if j < nums[i-1]:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]]\n",
    "        return dp[n][amount] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        total_sum = sum(nums)\n",
    "        if target > total_sum or target < -total_sum:\n",
    "            return 0\n",
    "\n",
    "        # 前 i 个数，组成 j 的数目\n",
    "        dp = [[0 for _ in range(-total_sum, total_sum + 1)] for _ in range(len(nums) + 1)]\n",
    "        dp[0][total_sum] = 1\n",
    "\n",
    "        for idx in range(len(nums)):\n",
    "            for res in range(-total_sum, total_sum + 1):\n",
    "                if dp[idx][res] != 0:\n",
    "                    dp[idx + 1][res + nums[idx]] += dp[idx][res]\n",
    "                    dp[idx + 1][res - nums[idx]] += dp[idx][res]\n",
    "\n",
    "        return dp[-1][target + total_sum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # a + b = nsum  a -b = target  => 2a = target + nsum\n",
    "        \n",
    "        nsum = sum(nums)\n",
    "        if (target + nsum) %2 != 0:\n",
    "            return 0\n",
    "        \n",
    "        mount =  (abs(target) + nsum)//2  #notice here\n",
    "        nlen = len(nums)\n",
    "        dp = [ [0] * (mount + 1) for i in range(nlen +1)  ]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,nlen +1):\n",
    "            for j in range(mount+1):\n",
    "                not_contain = dp[i-1][j]\n",
    "                contain = 0\n",
    "                if j >= nums[i-1]:\n",
    "                    contain = dp[i-1][j - nums[i-1]]  #notice\n",
    "                dp[i][j] = contain + not_contain\n",
    "        print(dp)\n",
    "        return dp[nlen][mount]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        Sum = sum(nums)\n",
    "        m, n = len(nums), 2 * Sum + 1\n",
    "        if Sum < target:\n",
    "            return 0\n",
    "\n",
    "        # 初始化\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] += 1 if j == Sum + nums[0] else 0\n",
    "            dp[0][j] += 1 if j == Sum - nums[0] else 0\n",
    "\n",
    "        # 求dp\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if j - nums[i] >= 0 and j + nums[i] < n:\n",
    "                    dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]\n",
    "                elif j - nums[i] >= 0:\n",
    "                    dp[i][j] = dp[i-1][j-nums[i]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j+nums[i]]\n",
    "        print(dp)\n",
    "        return dp[m - 1][Sum + target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        s = sum(nums)\r\n",
    "        if (target+s)%2 or target+s<0:\r\n",
    "            return 0\r\n",
    "        zheng = int((target+s)/2)\r\n",
    "        cache = [[0]*(zheng+1) for i in range(n)]\r\n",
    "        # @cache\r\n",
    "        def dfs(i,goal):    \r\n",
    "            # print(i,goal)\r\n",
    "            if i == n:\r\n",
    "                if goal == 0:\r\n",
    "                    return 1\r\n",
    "                return 0\r\n",
    "            if cache[i][goal]!= 0:\r\n",
    "                return cache[i][goal]\r\n",
    "            a = dfs(i+1,goal)\r\n",
    "            b = dfs(i+1,goal-nums[i])\r\n",
    "            #不选\r\n",
    "            cache[i][goal] = a+b\r\n",
    "            return a+b\r\n",
    "        \r\n",
    "        \r\n",
    "        return dfs(0,int(zheng))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def getSide(self, num):\n",
    "        \n",
    "        if num >= 0:\n",
    "            \n",
    "            return 0\n",
    "        \n",
    "        else: return 1\n",
    "        \n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        \n",
    "        maxSum = sum(nums)\n",
    "        \n",
    "        if abs(target) > maxSum:\n",
    "            \n",
    "            return 0\n",
    "        \n",
    "        A = [[[0,0]for i in range(maxSum+1)] for i in range(len(nums))]\n",
    "        \n",
    "        if nums[0] == 0:\n",
    "            A[0][nums[0]] = [2,2]\n",
    "        else:\n",
    "            A[0][nums[0]] = [1,1]\n",
    "            \n",
    "        for a in range(1,len(nums)):\n",
    "            for b in range(maxSum+1):\n",
    "                \n",
    "                cur = nums[a]\n",
    "                \n",
    "                if b+cur <= maxSum:\n",
    "                    A[a][b][0] = A[a][b][0] + A[a-1][b+cur][0]\n",
    "                \n",
    "                if abs(b-cur) <= maxSum:\n",
    "                    if b-cur <0:\n",
    "                        A[a][b][0] = A[a][b][0] + A[a-1][-(b-cur)][1]\n",
    "\n",
    "                    else:\n",
    "                        A[a][b][0] = A[a][b][0] + A[a-1][b-cur][0]\n",
    "                \n",
    "                if -b+cur <= maxSum and -b+cur >=0:\n",
    "                    A[a][b][1] = A[a][b][1] + A[a-1][-b+cur][0]\n",
    "                    \n",
    "                else:\n",
    "                    A[a][b][1] = A[a][b][1] + A[a-1][-(-b+cur)][1]\n",
    "            \n",
    "                if abs(-b-cur) <=maxSum:\n",
    "                    if -b-cur <0:\n",
    "                        A[a][b][1] = A[a][b][1] + A[a-1][-(-b-cur)][1]\n",
    "\n",
    "                    else:\n",
    "                        A[a][b][1] = A[a][b][1] + A[a-1][-b-cur][0]\n",
    "        \n",
    "        \n",
    "        return A[len(nums)-1][abs(target)][self.getSide(target)]\n",
    "            \n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 类似最后一颗石子重量2那题\n",
    "# 负号堆+target=正号堆\n",
    "# 注意dp[(0,-1)]=1 即背包为空，一开始可以不选\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        dp=defaultdict(int)\n",
    "        dp[(0,-1)]=1\n",
    "        n=len(nums)\n",
    "        if (sum(nums)+target)&1:\n",
    "            return 0\n",
    "        else:\n",
    "            vol=(sum(nums)+target)//2\n",
    "            for i in range(n):\n",
    "                for w in range(vol+1):\n",
    "                    if w<nums[i]:\n",
    "                        dp[(w,i)]=dp[(w,i-1)]\n",
    "                    else:\n",
    "                        dp[(w,i)]=dp[(w,i-1)]+dp[(w-nums[i],i-1)]\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[(vol,n-1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        self.memo = [[-1] * (20001) for _ in range(len(nums))]\n",
    "        return self.dp(nums, target, 0)\n",
    "    \n",
    "    def dp(self, nums, target, i):\n",
    "        if i >= len(nums):\n",
    "            if target == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        if self.memo[i][target + 10000] != -1:\n",
    "            return self.memo[i][target + 10000]\n",
    "        \n",
    "        self.memo[i][target + 10000] = self.dp(nums, target - nums[i], i + 1) + self.dp(nums, target + nums[i], i + 1)\n",
    "        return self.memo[i][target + 10000]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<abs(target):return 0\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 2**nums.count(0)\n",
    "        arr = tuple([i for i in nums if i>0])\n",
    "        @cache\n",
    "        def dfs(arr,tar):\n",
    "            if sum(arr)==abs(tar):return 1\n",
    "            if sum(arr)<abs(tar) or len(arr)==1:return 0\n",
    "            return dfs(arr[1:],tar-arr[0])+dfs(arr[1:],tar+arr[0])\n",
    "        ans = ans*dfs(arr,target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        numdict = {}\n",
    "        sumelse = sum(abs(nums[j]) for j in range(n))\n",
    "        @cache\n",
    "        def dfs(sumnum, i, sumelse):\n",
    "            if i == n:\n",
    "                if sumnum == target:\n",
    "                    return 1\n",
    "                return 0\n",
    "            if sumnum + sumelse < target or sumnum - sumelse > target:\n",
    "                return 0\n",
    "            return dfs(sumnum+nums[i], i+1, sumelse-abs(nums[i])) + dfs(sumnum-nums[i], i+1, sumelse-abs(nums[i]))\n",
    "        return dfs(0,0, sumelse)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        m,n = sum(nums),len(nums)\n",
    "        dp = {(0,0):1}\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(-m,m+1):\n",
    "                dp[(i,j)]=dp.get((i-1,j-nums[i-1]),0)+dp.get((i-1,j+nums[i-1]),0)\n",
    "        return dp.get((n,target),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "\n",
    "        dp = defaultdict(int)\n",
    "\n",
    "        dp[(0,0)] = 1\n",
    "        limit = sum(nums)\n",
    "        if target > limit or target < -limit:\n",
    "            return 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(-limit,limit+1):\n",
    "                dp[(i+1,j)] = dp[(i,j+nums[i])] + dp[(i,j-nums[i])]\n",
    "            \n",
    "        return dp[(len(nums),target)]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:\n",
    "        length, dp = len(nums), {(0,0): 1}\n",
    "        for i in range(1, length+1):\n",
    "            for j in range(-sum(nums), sum(nums) + 1):\n",
    "                dp[(i,j)] = dp.get((i - 1, j - nums[i-1]), 0) + dp.get((i - 1, j + nums[i-1]), 0)             \n",
    "        return dp.get((length, S), 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # map from length sum to count\n",
    "        dp = collections.Counter()  # (len, sum_of_length) -> count\n",
    "        dp[(0, 0)] = 1  # initilized as 0 length with sum of 0, get count 1\n",
    "        l = len(nums)\n",
    "        tmp = sum(nums)\n",
    "\n",
    "        for i in range(l):\n",
    "            # consider nums[i], length i + 1 subarrary\n",
    "\n",
    "            # possible j is enumerated\n",
    "            # not easy to fetch all values belonging to dp[(i), *]\n",
    "            for j in range(-tmp, tmp + 1, 1):\n",
    "                dp[(i + 1, j)] = dp[(i, j + nums[i])] + dp[(i, j - nums[i])]\n",
    "\n",
    "        return dp[(l, target)]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        target = sum(nums)-target\n",
    "        if target < 0 or target%2 !=0:\n",
    "            return 0\n",
    "        target //=2\n",
    "        # print(target)\n",
    "        # dp = [[0]*(target+1) for _ in range(n+1)]\n",
    "        # dp[0][0] = 1\n",
    "        # for i in range(1,n+1):\n",
    "        #     num = nums[i-1]\n",
    "        #     for j in range(target+1):\n",
    "        #         dp[i][j] = dp[i-1][j] #不选\n",
    "        #         if j>=num:#可选条件\n",
    "        #             dp[i][j] += dp[i-1][j-num]#加上可选\n",
    "        # print(dp)\n",
    "        # return dp[-1][-1]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,c):\n",
    "            if i<0:\n",
    "                if c == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            if c < nums[i]: #无法选，只能不选\n",
    "                return dfs(i-1,c)\n",
    "            return dfs(i-1,c)+dfs(i-1,c-nums[i]) #不选的方法+ 选的方案数\n",
    "        \n",
    "        return dfs(n-1, target)\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        num = sum(nums)\n",
    "        if (num - target) < 0 or (num - target) % 2 == 1:\n",
    "            return 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            if c < nums[i]:\n",
    "                return dfs(i-1, c) #只能不选\n",
    "            return dfs(i-1, c) + dfs(i-1, c - nums[i]) #选的方案数+不选的方案数\n",
    "        return dfs(len(nums)-1, (num-target)//2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        num = sum(nums)\n",
    "        if (num - target) < 0 or (num - target) % 2 == 1:\n",
    "            return 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            if c < nums[i]:\n",
    "                return dfs(i-1, c) #只能不选\n",
    "            return dfs(i-1, c) + dfs(i-1, c - nums[i]) #选的方案数+不选的方案数\n",
    "        return dfs(len(nums)-1, (num+target)//2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        target = sum(nums) - target\n",
    "        if target % 2 > 0 or target < 0: return 0\n",
    "        target = target // 2\n",
    "        @cache\n",
    "        def dfs(i, target):\n",
    "            if i == len(nums): return 1 if target == 0 else 0\n",
    "            if target < 0: return 0\n",
    "            return dfs(i+1, target-nums[i]) + dfs(i+1, target)\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        target += sum(nums)\n",
    "\n",
    "        if target < 0 or target % 2:\n",
    "\n",
    "            return 0\n",
    "\n",
    "        target //= 2\n",
    "\n",
    "\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "\n",
    "        def dfs(i, c):\n",
    "\n",
    "            if i < 0:\n",
    "\n",
    "                return 1 if c == 0 else 0\n",
    "\n",
    "            if c < nums[i]:\n",
    "\n",
    "                return dfs(i - 1, c)\n",
    "\n",
    "            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])\n",
    "\n",
    "        return dfs(len(nums) - 1, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        target += sum(nums)\n",
    "        if target < 0 or target % 2:\n",
    "            return 0\n",
    "        target //= 2\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            if c < nums[i]:\n",
    "                return dfs(i-1, c)\n",
    "            return dfs(i-1, c) + dfs(i-1, c-nums[i])\n",
    "        return dfs(n-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "from typing import List\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        \"\"\"\r\n",
    "        灵神教学：\r\n",
    "        总数：s = sum(nums)\r\n",
    "        正数：p\r\n",
    "        负数：s-p\r\n",
    "        p-(s-p) = target\r\n",
    "        p = (target+s)/2\r\n",
    "        该问题转化为找到数字之和为p\r\n",
    "        \"\"\"\r\n",
    "        s = sum(nums)\r\n",
    "        p = (target+s)/2\r\n",
    "        if (target+s)%2:\r\n",
    "            return 0\r\n",
    "        n = len(nums)   \r\n",
    "        @cache    \r\n",
    "        def dfs(i,t):\r\n",
    "            \"\"\"\r\n",
    "            定义dfs是前i个字符选出非负数之和为p的个数\r\n",
    "            \"\"\"\r\n",
    "            if i<0:# 注意，递归的出口是i<0不是t=0\r\n",
    "                return 1 if t==0 else 0\r\n",
    "            ans1 = 0\r\n",
    "            if t>=nums[i]:# t比当前值大才需要减，否则不用减\r\n",
    "                ans1 = dfs(i-1,t-nums[i])\r\n",
    "            # 第一个选了，第二个没选\r\n",
    "            return ans1+dfs(i-1,t)\r\n",
    "        return dfs(n-1,p)\r\n",
    "    \r\n",
    "    def findTargetSumWays_1(self, nums: List[int], target: int) -> int:\r\n",
    "        \"\"\"\r\n",
    "        ！！！递推版本\r\n",
    "        dfs(i,t) = dfs(i-1,t-nums[i])+dfs(i-1,t)\r\n",
    "        f[i][t] = f[i-1][t-nums[i]]+f[i-1][t]\r\n",
    "        f[i+1][t] = f[i][t-nums[i]]+f[i][t]\r\n",
    "        灵神教学：\r\n",
    "        总数：s = sum(nums)\r\n",
    "        正数：p\r\n",
    "        负数：s-p\r\n",
    "        p-(s-p) = target\r\n",
    "        p = (target+s)/2\r\n",
    "        该问题转化为找到数字之和为p\r\n",
    "        \"\"\"\r\n",
    "        s = sum(nums)\r\n",
    "        if (target+s)%2:\r\n",
    "            return 0\r\n",
    "        p = int((target+s)/2)\r\n",
    "        n = len(nums)\r\n",
    "        f = [[0] for _ in range(p+1)]*(n+1)\r\n",
    "        for i in range(n+1):\r\n",
    "            for j in range(p+1):\r\n",
    "                f[i+1][j] = f[i][j-nums[i]]+f[i][j]\r\n",
    "        return f[n][p]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        t = target + sum(nums)\n",
    "        if t < 0 or t % 2:\n",
    "            return 0\n",
    "        t /= 2\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c==0 else 0\n",
    "            if c < nums[i]:\n",
    "                return dfs(i-1, c)\n",
    "            return dfs(i-1, c) + dfs(i-1, c-nums[i])\n",
    "        return dfs(n-1, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        from itertools import accumulate\n",
    "        from functools import cache\n",
    "        sums = [0] + list(accumulate(nums))\n",
    "        self.res = 0\n",
    "        self.n = len(nums)\n",
    "        @cache\n",
    "        def recur(cur,start):\n",
    "            #print(cur,start)\n",
    "            if start == self.n:\n",
    "                if cur == target:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res = 0\n",
    "            if sums[-1]-sums[start] >= target-cur:\n",
    "                res += recur(cur+nums[start],start+1)\n",
    "                res += recur(cur-nums[start],start+1)\n",
    "            return res\n",
    "        res = recur(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "\n",
    "    def getAnswer(self, c, nums, index):\n",
    "\n",
    "        if index >= len(nums):\n",
    "            if c == 0:\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        if nums[index] > c:\n",
    "            return self.getAnswer(c, nums, index + 1)\n",
    "\n",
    "        return self.getAnswer(c, nums, index + 1) + self.getAnswer(c - nums[index], nums, index + 1)\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "\n",
    "        p = (target + s) / 2\n",
    "\n",
    "        if (target + s) % 2 == 1 or (target + s) < 0:\n",
    "            return 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, index):\n",
    "            if index >= len(nums):\n",
    "                return 1 if p == 0 else 0\n",
    "            if nums[index] > p:\n",
    "                return dfs(p, index + 1)\n",
    "            return dfs(p, index + 1) + dfs(p-nums[index], index+1)\n",
    "        return dfs(p, 1) + dfs(p-nums[0], 1)\n",
    "\n",
    "\n",
    "        # return self.getAnswer(p, nums, 1) + self.getAnswer(p - nums[0], nums, 1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # 构造和为 target 的方案数\n",
    "        # 设正 p， 负数s-p => p - (s-p) = t\n",
    "        # 2p-s=t => p=(t+s)/2\n",
    "\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if (target + s) % 2: \n",
    "            return 0\n",
    "        target = (target + s) / 2\n",
    "        # 从[0, i]选出和为 target 的方案\n",
    "        @cache \n",
    "        def dfs(i: int, target: int) -> int:\n",
    "            if i < 0: return 1 if target == 0 else 0\n",
    "            if target < 0: return 0\n",
    "            res = dfs(i-1, target)\n",
    "            res += dfs(i-1, target - nums[i])\n",
    "            return res\n",
    "        return dfs(n-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        p = target + sum(nums)\n",
    "        if target < 0 and p % 2:\n",
    "            return 0\n",
    "        c = p / 2\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, c1):\n",
    "            if i < 0:\n",
    "                return 1 if c1==0 else 0\n",
    "            if c1 < nums[i]:\n",
    "                return dp(i-1, c1)\n",
    "            return dp(i-1, c1) + dp(i-1, c1-nums[i])\n",
    "        return dp(len(nums)-1, c)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # sums = [nums[0], -nums[0]]\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     tmp = []\n",
    "        #     for sum_ in sums:\n",
    "        #         tmp.append(sum_ + nums[i])\n",
    "        #         tmp.append(sum_ - nums[i])\n",
    "        #     sums = tmp\n",
    "        # return sum(1 for sum_ in sums if sum_ == target)\n",
    "        n = len(nums)\n",
    "        sum_ = sum(nums) + target\n",
    "        if sum_ % 2 != 0:\n",
    "            return 0\n",
    "\n",
    "        lookup = {}\n",
    "        \n",
    "        def dfs(i, sum_):\n",
    "            nonlocal lookup\n",
    "            if (i, sum_) in lookup:\n",
    "                return lookup[(i, sum_)]\n",
    "            if i < 0:\n",
    "                return 1 if sum_ == 0 else 0\n",
    "            lookup[(i, sum_)] = dfs(i-1, sum_) + dfs(i-1, sum_ - nums[i])\n",
    "            return lookup[(i, sum_)]\n",
    "    \n",
    "        return dfs(n-1, sum_//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        sumV = sum(nums)\n",
    "        value = (sumV + target)/2\n",
    "        n = len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i == n:\n",
    "                return 1 if c == value else 0 \n",
    "            if c+nums[i]>value:\n",
    "                return dfs(i+1,c)\n",
    "            return dfs(i+1,c+nums[i])+dfs(i+1,c)\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "from typing import List\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def M1(self, nums: List[int], target: int) -> int:\r\n",
    "        '''\r\n",
    "        行为：\r\n",
    "            考察的数字i\r\n",
    "            当前和\r\n",
    "            操作 + - \r\n",
    "        \r\n",
    "        状态：当前数字为nums[i], 需要累加到target，的表达式数目\r\n",
    "\r\n",
    "        state(i, sum) = \r\n",
    "            # 给num增加减号\r\n",
    "            state(i, sum - num[i])\r\n",
    "            # 给num加号\r\n",
    "            state(i, sum + num[i])\r\n",
    "        \r\n",
    "        解：target == sum, and i == len()\r\n",
    "        '''\r\n",
    "        nums.sort() # 优化\r\n",
    "        @cache\r\n",
    "        def state(i, targetSum):\r\n",
    "            if i == len(nums):\r\n",
    "                if targetSum == target:\r\n",
    "                    return 1\r\n",
    "                return 0\r\n",
    "\r\n",
    "            res = 0\r\n",
    "            # 扩展新状态\r\n",
    "\r\n",
    "            # 优化\r\n",
    "            # if targetSum < target: # 没必要再加了，后面可能减回来？\r\n",
    "            res += state(i+1, targetSum + nums[i])\r\n",
    "            \r\n",
    "            res += state(i+1, targetSum - nums[i])\r\n",
    "\r\n",
    "            return res\r\n",
    "        # 初始状态\r\n",
    "        res = state(0, 0)\r\n",
    "        print(state.cache_info())\r\n",
    "        return res\r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        return self.M1(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        result_map = {}\n",
    "\n",
    "        def recur(nums, idx, target):\n",
    "            if (idx, target) in result_map:\n",
    "                return result_map[(idx, target)]\n",
    "\n",
    "            if idx == 0:\n",
    "                n_expr = 0\n",
    "                if target == nums[0]:\n",
    "                    n_expr += 1\n",
    "                if target == -nums[0]:\n",
    "                    n_expr += 1\n",
    "                return n_expr\n",
    "\n",
    "            n_expr_if_pos = recur(nums, idx-1, target - nums[idx])\n",
    "            n_expr_if_neg = recur(nums, idx-1, target + nums[idx])\n",
    "            res = n_expr_if_pos + n_expr_if_neg\n",
    "            result_map[(idx, target)] = res\n",
    "\n",
    "            return res\n",
    "\n",
    "        return recur(nums, len(nums)-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # p为正数和\n",
    "        # s为数组总和\n",
    "        # 负数和为p-s\n",
    "        # 所以2p-s=target\n",
    "        # p=target+s//2\n",
    "        n=len(nums)\n",
    "        target+=sum(nums)\n",
    "        target/=2\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i<0:\n",
    "                return 1 if c==0 else 0\n",
    "            if c<nums[i]:\n",
    "                return dfs(i-1,c)\n",
    "            return dfs(i-1,c)+dfs(i-1,c-nums[i])\n",
    "        return dfs(n-1,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        t = sum(nums)-target\r\n",
    "        che = {}\r\n",
    "        def dfs(i,v):\r\n",
    "            if i==0:return 1 if v==0 else 0\r\n",
    "            if (i,v) in che:return che[(i,v)]\r\n",
    "            res = dfs(i-1,v-(nums[i-1]*2))+dfs(i-1,v)\r\n",
    "            che[(i,v)] = res\r\n",
    "            return res\r\n",
    "        return dfs(len(nums),t)\r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "\n",
    "        total = sum(nums)\n",
    "        target = abs(target)\n",
    "        if target > total: return 0\n",
    "        # target = 正数和 - 负数和 = x - y 而已知x与y的和是数组总和：x + y = total 可以求出 x = (target + total) / 2 \n",
    "        # 如果x不是整数，也就是target + total不是偶数，不可能实现，返回0\n",
    "        if (target + total) % 2: return 0\n",
    "\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(u, cur):\n",
    "            if (u, cur) in cache:\n",
    "                return cache[(u, cur)]\n",
    "            if u == n:\n",
    "                # cache[(u, cur)] = 1 if cur == target else 0\n",
    "                # return cache[(u, cur)]\n",
    "                return 1 if cur == target else 0\n",
    "\n",
    "            l = dfs(u+1, cur+nums[u])\n",
    "            r = dfs(u+1, cur-nums[u])\n",
    "            cache[(u, cur)] = l+r\n",
    "            return cache[(u, cur)]\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        total = sum(nums)\n",
    "        n = len(nums)\n",
    "        if total < target or target < -total:\n",
    "            return 0\n",
    "        if total == target or -total == target:\n",
    "            if target == 0:\n",
    "                return 2**n\n",
    "            #else:\n",
    "                #return 1\n",
    "        @cache\n",
    "        def dfs(cur,end):\n",
    "            if end == 0:\n",
    "                if cur == 0 and nums[end] == 0:\n",
    "                    return 2\n",
    "                if cur == nums[end]:\n",
    "                    return 1\n",
    "                elif cur == -nums[end]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            #if nums[end] == 0:\n",
    "                #return 2*dfs(cur,end-1)\n",
    "            return dfs(cur-nums[end],end-1) + dfs(cur+nums[end],end-1)\n",
    "        return dfs(target,n-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        sum_ = sum(nums)\n",
    "        target += sum_\n",
    "        if target % 2 == 1:\n",
    "            return 0\n",
    "        \n",
    "        target //= 2\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            \"\"\"\n",
    "            表示从前i个数中选取数字能得到和为j的个数\n",
    "            \"\"\"\n",
    "            if i == -1:\n",
    "                return 1 if j == 0 else 0\n",
    "            # if nums[i] > j:\n",
    "            #     return dfs(i-1, j)\n",
    "            return dfs(i-1, j-nums[i]) + dfs(i-1, j)\n",
    "\n",
    "        return dfs(len(nums)-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = target + sum(nums)\n",
    "        if s % 2 != 0:\n",
    "            return 0\n",
    "        else:\n",
    "            s = s // 2\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])\n",
    "        return dfs(n - 1, s)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # sums = [nums[0], -nums[0]]\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     tmp = []\n",
    "        #     for sum_ in sums:\n",
    "        #         tmp.append(sum_ + nums[i])\n",
    "        #         tmp.append(sum_ - nums[i])\n",
    "        #     sums = tmp\n",
    "        # return sum(1 for sum_ in sums if sum_ == target)\n",
    "        n = len(nums)\n",
    "        sum_ = sum(nums) + target\n",
    "        if sum_ % 2 != 0:\n",
    "            return 0\n",
    "\n",
    "        lookup = {}\n",
    "        \n",
    "        def dfs(i, sum_):\n",
    "            nonlocal lookup\n",
    "            if (i, sum_) in lookup:\n",
    "                return lookup[(i, sum_)]\n",
    "            if i < 0:\n",
    "                return 1 if sum_ == 0 else 0\n",
    "            r1 = dfs(i-1, sum_)\n",
    "            r2 = dfs(i-1, sum_ - nums[i])\n",
    "            lookup[(i-1, sum_)] = r1\n",
    "            lookup[(i-1, sum_ - nums[i])] = r2\n",
    "            return r1 + r2\n",
    "    \n",
    "        return dfs(n-1, sum_//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        dict={}\r\n",
    "        def dp(i,j):\r\n",
    "            if (i,j) in dict:\r\n",
    "                return dict[(i,j)]\r\n",
    "            if i==0:\r\n",
    "                ans=int(nums[i]==j)+int(nums[i]==-1*j)\r\n",
    "            else:\r\n",
    "                ans=dp(i-1,j+nums[i])+dp(i-1,j-nums[i])\r\n",
    "            dict[(i,j)]=ans\r\n",
    "            return ans\r\n",
    "        return dp(len(nums)-1,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,target):\n",
    "            #前i个的子问题，由前一个状态转移过来\n",
    "            if i==0:\n",
    "                if nums[0]==0==target:\n",
    "                    return 2\n",
    "                else:\n",
    "                    return 1 if (abs(nums[0])-abs(target))==0 else 0\n",
    "            return dfs(i-1,target+nums[i])+dfs(i-1,target-nums[i])\n",
    "        return dfs(len(nums)-1,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "from typing import List\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def M1(self, nums: List[int], target: int) -> int:\r\n",
    "        '''\r\n",
    "        行为：\r\n",
    "            考察的数字i\r\n",
    "            当前和\r\n",
    "            操作 + - \r\n",
    "        \r\n",
    "        状态：当前数字为nums[i], 需要累加到target，的表达式数目\r\n",
    "\r\n",
    "        state(i, sum) = \r\n",
    "            # 给num增加减号\r\n",
    "            state(i, sum - num[i])\r\n",
    "            # 给num加号\r\n",
    "            state(i, sum + num[i])\r\n",
    "        \r\n",
    "        解：target == sum, and i == len()\r\n",
    "        '''\r\n",
    "        @cache\r\n",
    "        def state(i, targetSum):\r\n",
    "            if i == -1:\r\n",
    "                if targetSum == 0:\r\n",
    "                    return 1\r\n",
    "                return 0\r\n",
    "            res = 0\r\n",
    "            # 扩展新状态\r\n",
    "            # 优化\r\n",
    "            # if targetSum < target: # 没必要再加了，后面可能减回来\r\n",
    "            res += state(i-1, targetSum + nums[i])\r\n",
    "            res += state(i-1, targetSum - nums[i])\r\n",
    "            return res\r\n",
    "        \r\n",
    "        # 优化\r\n",
    "        totalSum = sum(nums) + target\r\n",
    "        if totalSum < 0 or totalSum % 2:\r\n",
    "            return 0\r\n",
    "        # 初始状态\r\n",
    "        res = state(len(nums) - 1, target)\r\n",
    "        # print(state.cache_info())\r\n",
    "        return res\r\n",
    "    def M11(self, nums: List[int], target: int) -> int:\r\n",
    "        ''' 递推\r\n",
    "    \r\n",
    "        dp[i][j] = dp[i-1][j-num] + dp[i-1][j + num]\r\n",
    "\r\n",
    "        dp[0][j]\r\n",
    "        '''\r\n",
    "        target += sum(nums)\r\n",
    "        if target < 0 or target % 2:\r\n",
    "            return 0\r\n",
    "        target //= 2\r\n",
    "\r\n",
    "        n = len(nums)\r\n",
    "        f = [[0] * (target + 1) for _ in range(n + 1)]\r\n",
    "        f[0][0] = 1\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            for c in range(target + 1):\r\n",
    "                if c < x:\r\n",
    "                    f[i + 1][c] = f[i][c]\r\n",
    "                else:\r\n",
    "                    f[i + 1][c] = f[i][c] + f[i][c - x]\r\n",
    "        return f[n][target]\r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        return self.M1(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\r\n",
    "        res = []\r\n",
    "        sum_nums = [sum(nums[i:]) for i in range(len(nums))]\r\n",
    "        for i, num in enumerate(nums):\r\n",
    "            if res == []:\r\n",
    "                res = [num, -num]\r\n",
    "            else:\r\n",
    "                tmp = []\r\n",
    "                for r in res:\r\n",
    "                    if r> target+sum_nums[i] or r< target-sum_nums[i]:\r\n",
    "                        continue\r\n",
    "                    tmp.append(r+num)\r\n",
    "                    tmp.append(r-num)\r\n",
    "                res = tmp\r\n",
    "        return res.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        # @cache\n",
    "        @lru_cache(maxsize=None)\n",
    "        def back_track(i, tmp):\n",
    "            if i == n and tmp == target:\n",
    "                return 1\n",
    "            elif i == n:\n",
    "                return 0\n",
    "            else:\n",
    "                return back_track(i + 1, tmp + nums[i]) + back_track(i + 1, tmp - nums[i])\n",
    "        diff = sum(nums) - target\n",
    "        if diff < 0 or diff % 2 != 0:\n",
    "            return 0\n",
    "        return back_track(0, 0)\n",
    "\n",
    "        # Method 2\n",
    "        # target += sum(nums)\n",
    "        # if target < 0 or target % 2:\n",
    "        #     return 0\n",
    "        # target //= 2\n",
    "\n",
    "        # f = [1] + [0] * target\n",
    "        # for x in nums:\n",
    "        #     for c in range(target, x - 1, -1):\n",
    "        #         f[c] += f[c - x]\n",
    "        # return f[target]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        lenq, sumq = len(nums), sum(nums)\n",
    "        target = abs(target)\n",
    "        if target > sumq: return 0\n",
    "\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(i, curSum):\n",
    "            if (i, curSum) in cache: return cache[(i, curSum)]\n",
    "            if i == lenq: return 1 if curSum == target else 0\n",
    "\n",
    "            l = dfs(i+1, curSum + nums[i])\n",
    "            r = dfs(i+1, curSum - nums[i])\n",
    "            cache[(i, curSum)] = l+r\n",
    "            return cache[(i, curSum)]\n",
    "\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        temp=target+sum(nums)\n",
    "        if temp < 0 or temp % 2:\n",
    "            return 0\n",
    "        k = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(val, cur):\n",
    "            if cur==k:\n",
    "                return 1 if val == target else 0\n",
    "            else:\n",
    "                w = nums[cur]\n",
    "                return dfs(val+w, cur+1) + dfs(val-w, cur+1)\n",
    "\n",
    "        ret = dfs(0, 0)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        recursion_dict = {}\n",
    "        def findtargetwumways_recursion(nums, state, k):\n",
    "            if k == len(nums) and state == target:\n",
    "                return 1\n",
    "            if k == len(nums):\n",
    "                return 0\n",
    "            if (state, k) in recursion_dict:\n",
    "                return recursion_dict[(state, k)]\n",
    "            r1 = findtargetwumways_recursion(nums, state - nums[k], k + 1)\n",
    "            r2 = findtargetwumways_recursion(nums, state + nums[k], k + 1)\n",
    "            recursion_dict[(state, k)] = r1 + r2\n",
    "            return r1 + r2\n",
    "\n",
    "        return findtargetwumways_recursion(nums, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        memo = {}  # 用字典保存中间结果\n",
    "\n",
    "        def dfs(i, cur):\n",
    "            if i == len(nums):\n",
    "                return 1 if cur == target else 0\n",
    "\n",
    "            if (i, cur) in memo:\n",
    "                return memo[(i, cur)]\n",
    "\n",
    "            # 递归搜索周围节点\n",
    "            result = dfs(i + 1, cur + nums[i]) + dfs(i + 1, cur - nums[i])\n",
    "            memo[(i, cur)] = result\n",
    "\n",
    "            return result\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
